package everyday;

import java.util.ArrayList;
import java.util.List;

public class T1377 {
    int n;
    int t;
    int target;
    List<ArrayList<Integer>> e;
    int r = 0;

    public double frogPosition(int n, int[][] edges, int t, int target) {
        if (target == 1 && edges.length == 0) return 1;
        this.n = n;
        this.t = t;
        this.target = target;
        e = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            e.add(new ArrayList<>());
        }
        for (int[] edge : edges) {
            e.get(edge[0]).add(edge[1]);
            e.get(edge[1]).add(edge[0]);
        }
        dfs(-1, 1, 0, 1);
        return r;
    }

    public void dfs(int f, int a, int d, int es) {
        System.out.println(a + "  " + d + "  " + es);
        if (d == t ) {
            if (a==target)r = es;
            return;
        }
        int len = e.get(a).size();
        if (len == 1 && a == target) r = es;
        for (int i = 0; i < len; i++) {
            if (e.get(a).get(i) != f) {
                dfs(a, e.get(a).get(i), d + 1, es * (len - a == 0 ? 0 : 1));
            }
        }
    }
}
